package com.example.myletcodelearing.chaintable

import kotlin.jvm.JvmOverloads
import kotlin.jvm.JvmStatic
import java.lang.RuntimeException

/**
 * @author tgw
 * @date 2022/7/30
 * @describe
 */
class StaticLinkList<E> @JvmOverloads constructor(private val maxSize: Int = 1000) {
    private val nodes: Array<SNode<E?>?>

    inner class SNode<E>(var data: Student?, var cur: Int)

    /**
     * 获取第i个元素的下标
     */
    fun getIndex(i: Int): Int {
        if (i < 1 || i > length) throw RuntimeException("查找位置错误！")
        var k: Int = nodes[maxSize - 1]?.cur?:0
        for (j in 1 until i) k = nodes[k]?.cur?:0
        return k
    }

    /**
     * 获取第i个元素
     */
    fun getElement(i: Int): SNode<E?>? {
        return nodes[getIndex(i)]
    }

    /**
     * 返回可分配结点下标
     *
     * i 将要插入的数据对象
     *
     *  nodes[0]?.cur = 将下一个为空数据的节点位置记录
     */
    fun malloc_sll(): Int {
        val i: Int = nodes[0]?.cur?:0
        nodes[0]?.cur = nodes[i]?.cur?:0 //第i个分量要拿来用了，所以指向下一个分量
        //注意，不是nodes[0].cur=nodes[0].cur+1，下一个分量不一定就是下标加一;
        return i
    }

    /**
     * 插入操作,i代表第i个位置，而不是下标
     * 注意插入到第一个位置的特殊性
     *
     * 头结点的cur存储下一个还没有数据的位置
     * nodes[p]存储上次插入数据的位置
     */
    fun listInsert(i: Int, e: Student) {
        if (i < 1 || i > length + 1) throw RuntimeException("插入位置错误！")
        if (length == maxSize - 2) throw RuntimeException("表已满，无法插入！")
        val j = malloc_sll()
        println("listInsert--malloc_sll$j")
        nodes[j]?.data = e
        val p: Int ////第i-1个元素的下标
        p = if (i == 1) {
            maxSize - 1
        } else {
            getIndex(i - 1)
        }
        nodes[j]?.cur = nodes[p]?.cur?:0
        nodes[p]?.cur = j
    }

    /**
     * 删除第i个位置的结点
     */
    fun listDelete(i: Int): SNode<E?>? {
        if (i < 1 || i > length) throw RuntimeException("删除位置错误！")
        val m = getIndex(i)
        val p: Int //第i-1个元素的下标
        p = if (i == 1) {
            maxSize - 1
        } else {
            getIndex(i - 1)
        }
        nodes[p]?.cur = nodes[m]?.cur?:0
        free_sll(m)
        return nodes[m]
    }

    /**
     * 将下标为i元素回收到备用链表中
     */
    fun free_sll(i: Int) {
        nodes[i]?.cur = nodes[0]?.cur?:0
        nodes[0]?.cur = i
    }

    /**
     * 返回静态链表的长度
     */
    val length: Int
        get() {
            var length = 0
            var i: Int = nodes[maxSize - 1]?.cur?:0
            while (i != 0) {
                i = nodes[i]?.cur?:0
                length++
            }
            return length
        }

    init {
        nodes = arrayOfNulls<SNode<E?>>(maxSize)//泛型的数组建立似乎有些问题
        for (i in 0 until maxSize - 1) {
            nodes[i] = SNode<E?>(null, i + 1)
        }
        nodes[maxSize - 1] = SNode<E?>(null, 0)
    }
}

object StaticLinkListTest {
    @JvmStatic
    fun main(args: Array<String>) {
        val students = StaticLinkList<Student>()
        println("——————————插入1到5,并读取内容——————————")
//        val stus = arrayOf(
//            Student("小A", 11), Student("小B", 12), Student("小C", 13),
//            Student("小D", 14), Student("小E", 151)
//        )
        val stus = arrayOf(
            Student("小A", 11), Student("小B", 12), Student("小C", 13),
            Student("小D", 14), Student("小E", 151)
        )
        for (i in 1..5) students.listInsert(1, stus[i - 1])
        students.listInsert(2,  Student("小5A", 11))
        students.listInsert(1,  Student("小5A", 11))
        println("表长：" + students.length)
        var stu: Student?
        for (i in 1..5) {
            stu = students.getElement(i)?.data
            println("第" + i + "个位置为：" + stu?.name)
        }
        println("——————————删除小B、小E——————————")
//        stu = students.listDelete(2)?.data
//        println("已删除：" + stu?.name)
//        stu = students.listDelete(4)?.data
//        println("已删除：" + stu?.name)
//        println("当前表长：" + students.length)
//        for (i in 1..students.length) {
//            stu = students.getElement(i)?.data
//            println("第" + i + "个位置为：" + stu?.name)
//        }
        println("表长：" + students.length)
    }
}

class Student(var name: String, var age: Int)